package SwordOffer;

public class Sword_Offer_14_I {

    public int cuttingRope(int n) {
        int res = 0;
        int[] array = new int[n+1];
        for (int i = 2; i <= n; i++) {
            int max = 0;
            for (int j = i - 1; j >= 1; j--) {
                max = Math.max(Math.max((i - j) * array[j], (i - j) * j), max);
            }
            array[i] = max;
            res = Math.max(max, res);
        }
        return res;
    }

    public static void main(String[] args) {
        Sword_Offer_14_I model = new Sword_Offer_14_I();
//        System.out.println(model.cuttingRope(2));
        System.out.println(model.cuttingRope(10));
        System.out.println(model.cuttingRope(58));
    }
}
